1. Field of the Invention
The present invention relates generally to computer networks, and more specifically, to a method and apparatus for configuring a memory device to efficiently perform matches against long input strings, such as network messages.
2. Background Information
A computer network typically comprises a plurality of interconnected entities that transmit (i.e., xe2x80x9csourcexe2x80x9d) or receive (i.e., xe2x80x9csinkxe2x80x9d) data frames. A common type of computer network is a local area network (xe2x80x9cLANxe2x80x9d) which typically refers to a privately owned network within a single building or campus. LANs employ a data communication protocol (LAN standard), such as Ethernet, FDDI or Token Ring, that defines the functions performed by the data link and physical layers of a communications architecture (i.e., a protocol stack), such as the Open Systems Interconnection (OSI) Reference Model. In many instances, multiple LANs may be interconnected by to form a wide area network (xe2x80x9cWANxe2x80x9d), metropolitan area network (xe2x80x9cMANxe2x80x9d) or intranet. These LANs and/or WANs, moreover, may be coupled through one or more gateways to the Internet.
Each network entity often includes network communication software, which operates in accordance with the Transmission Control Protocol/Internet Protocol (TCP/IP). TCP/IP basically consists of a set of rules defining how entities interact with each other. In particular, TCP/IP defines a series of communication layers, including a transport layer and a network layer. At the transport layer, TCP/IP includes both the User Datagram Protocol (UDP), which is a connectionless transport protocol, and the Transmission Control Protocol (TCP) which is a reliable, connection-oriented transport protocol. When a process at one network entity wishes to communicate with another entity, it formulates one or more messages and passes them to the upper layer of its TCP/IP communication stack. These messages are passed down through each layer of the stack where they are encapsulated into packets and frames. Each layer also adds information in the form of a header to the messages. The frames are then transmitted over the network links as bits. At the destination entity, the bits are re-assembled and passed up the layers of the destination entity""s communication stack. At each layer, the corresponding message headers are stripped off, thereby recovering the original message which is handed to the receiving process.
One or more intermediate network devices are often used to couple LANs together and allow the corresponding entities to exchange information. For example, a bridge may be used to provide a xe2x80x9cbridgingxe2x80x9d function between two or more LANs. Alternatively, a switch may be utilized to provide a xe2x80x9cswitchingxe2x80x9d function for transferring information, such as data frames or packets, among entities of a computer network. Typically, the switch is a computer having a plurality of ports that couple the switch to several LANs and to other switches. The switching function includes receiving messages at a source port and transferring them to at least one destination port for receipt by another entity. Switches may operate at various levels of the communication stack. For example, a switch may operate at layer 2 which, in the OSI Reference Model, is called the data link layer and includes the Logical Link Control (LLC) and Media Access Control (MAC) sub-layers.
Other intermediate devices, commonly referred to as routers, may operate at higher communication layers, such as layer 3 which, in TCP/IP networks corresponds to the Internet Protocol (IP) layer. IP message packets include a corresponding header which contains an IP source address and an IP destination address. Routers or layer 3 switches may re-assemble or convert received data frames from one LAN standard (e.g., Ethernet) to another (e.g. Token Ring). Thus, layer 3 devices are often used to interconnect dissimilar subnetworks. Some layer 3 intermediate network devices may also examine the transport layer headers of received messages to identify the corresponding TCP or UDP port numbers being utilized by the corresponding network entities. Such extended-capability devices are often referred to as Layer 4, Layer 5, Layer 6 or Layer 7 switches or Network Appliances. Many applications are assigned specific, fixed TCP and/or UDP port numbers in accordance with Request for Comments (RFC) 1700. For example, TCP/UDP port number 80 corresponds to the hyper text transport protocol (HTTP), while port number 21 corresponds to file transfer protocol (ftp) service.
FIG. 1 is a partial block diagram of a Network Layer packet 100 corresponding to the Internet Protocol. Packet 100 includes a protocol field 104, an IP source address (SA) field 106, an IP destination address (DA) field 108 and a data field 110, among others. FIG. 2 is a partial block diagram of a Transport Layer packet 200. Packet 200 includes a source port field 202, a destination port field 204 and a data field 206, among others. As indicated above, Fields 202 and 204 identify the local end points of the connection between the communicating entities and may include flow information and certain predefined or dynamically agreed-upon TCP or UDP port numbers.
Access Control Lists
Some networking software, including the Internetwork Operating System (IOS(copyright)) from Cisco Systems, Inc., supports the creation of access control lists or filters, which are typically used to prevent certain traffic from entering or exiting a network. In particular, certain layer 3 intermediate devices utilize access control lists to decide whether received messages should be forwarded or filtered (i.e., dropped) based on certain pre-defined criteria. The criteria may be IP source address, IP destination address, or upper-layer application based on TCP/UDP port numbers. For example, an access control list may allow e-mail to be forwarded, but cause all Telnet traffic to be dropped. Access control lists may be established for both inbound and outbound traffic and are most commonly configured at border devices (i.e., gateways or firewalls) to provide security to the network.
To generate an access control list, a network administrator typically defines a sequence of criteria statements using a conventional text editor or graphical user interface (GUI). As each subsequent statement is defined, it is appended to the end of the list. The completed list is then downloaded to the desired layer 3 intermediate device where it may be stored in the device""s non-volatile RAM (NVRAM) typically as a linked list. Upon initialization, the intermediate device copies the access control list to its dynamic memory. When a packet is subsequently received at a given interface of the device, a software module of IOS(copyright) tests the received packet against each criteria statement in the list. That is, the statements are checked in the order presented by the list. Once a match is found, the corresponding decision or action (e.g., permit or deny) is returned and applied to the packet. In other words, following a match, no more criteria statements are checked. Accordingly, at the end of each access control list a xe2x80x9cdeny all trafficxe2x80x9d statement is often added. Thus, if a given packet does not match any of the previous criteria statements, the packet will be discarded.
Currently, access control lists are used primarily to provide security. Thus, for a given interface, only a single list is evaluated per direction. The lists, moreover, are relatively short. Nevertheless, the evaluation of such lists by software modules can significantly degrade the intermediate device""s performance (e.g., number of packets processed per second). This degradation in performance has been accepted mainly due to a lack of acceptable alternatives. It is proposed, however, to expand the use of access control lists for additional features besides just security decisions. For example, access control lists may also be used to determine whether a given packet should be encrypted and/or whether a particular quality of service (QoS) treatment should be applied. Accordingly, it is anticipated that multiple access control lists may be assigned to a single interface. As additional access control lists are defined and evaluated per packet, the reduction in performance will likely reach unacceptable levels.
In addition, the message fields that may be evaluated by ACLs include IP source address, IP destination address, protocol, TCP/UDP source port, TCP/UDP destination port, virtual local area network (VLAN) identifier, differentiated services codepoint (DSCP), and the physical port on which the message was received. Under version 4 of the Internet Protocol (IPv4), IP source and destination addresses are 32 bits in length. Accordingly, the above information, which is often referred to as the flow label, adds up to approximately 133 bits. With version 6 of the Internet Protocol (IPv6), however, IP addresses are 128 bits long. Assuming the same fields are to be evaluated, the labels being evaluated are now approximately 336 bits long. It is also desirable in certain situations to evaluate higher-level messages, e.g., up to layer 7, which is the application layer. This would further increase the amount of information, and thus the number of bits, being evaluated. The longer the flow label, moreover, the more time that is required for software-based solutions to evaluate the corresponding ACL.
Accordingly, a need exists for a mechanism that can search long strings of data (e.g., 366 bits or more) efficiently and at relatively high-speed.
Briefly, the invention relates to a method and apparatus for efficiently organizing and storing data or information for subsequent searching. According to the invention, a storage facility includes one or more an associative memory devices, such as a ternary content addressable memory (TCAM). The TCAM is divided into a plurality of stages that are interconnected in a cascading fashion. To improve searching efficiency, the data or information to be stored into the TCAM for subsequent searching is initially translated into a first Boolean representation. In the preferred embodiment, the first Boolean representation is a binary decision diagram (BDD). Before loading the BDD into the associative memory device, the BDD is partitioned into a plurality of segments. Each segment, moreover, defines one or more outputs, and the outputs from one BDD segment define the inputs to the next BDD segment. After partitioning the BDD and identifying the resulting outputs, each BDD segment along with its corresponding outputs is mapped into a particular stage of the TCAM. The TCAM is then ready for matching.
Specifically, a network message may be matched against the information in the TCAM to locate a matching entry. The matching entry preferably specifies the particular action (e.g., drop, forward, delay, encrypt, etc.) that is to be applied to this message. To search the TCAM, a first portion of the network message is input to the first TCAM stage. The output from the first TCAM stage is then input into the second TCAM stage along with a second portion of the network message. The passing of outputs from an upstream TCAM stage to a downstream TCAM stage along with a new message portion is repeated until the entire network message has been evaluated within the TCAM and the final output of the TCAM is a particular action to be applied to the message.
In the preferred embodiment, the storage facility is incorporated into an intermediate network device, such as a switch-router, that processes Internet Protocol Version 6 (IPv6) messages. Furthermore, the data or information being loaded into the TCAM for subsequent searching is preferably one or more access control lists (ACLs). By partitioning the ACLs into multiple segments and defining output/input values between adjacent segments, the statements of the ACLs being searched within the TCAM, which include IPv6 addresses, can be longer than the width of the individual TCAM stages. For example, with the present invention, ACL statements that are more than 300 bits in length can nonetheless be organized into a TCAM whose individual stages are only 144 bits wide, thereby taking advantage of currently available components and reducing overall power consumption.